package pers.qianyu.month_202102.date_20210214;

import org.junit.*;

import java.util.*;

/**
 * 765. 情侣牵手
 * https://leetcode-cn.com/problems/couples-holding-hands/
 * - 贪心
 *
 * @author mizzle rain
 * @date 2021-02-14 10:48
 */
public class MinSwapsCouples4 {
    public int minSwapsCouples(int[] row) {
        int n = row.length;
        int res = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) map.put(row[i], i);
        for (int i = 0; i < n; i += 2) {
            int target = row[i] ^ 1;
            if (target != row[i + 1]) {
                int idx = map.get(target);
                int temp = row[idx];
                row[idx] = row[i + 1];
                row[i + 1] = temp;
                // 注意更新哈希表
                map.put(row[i + 1], i + 1);
                map.put(row[idx], idx);
                //System.out.println(Arrays.toString(row) + " " + i);
                res++;
            }
        }
        return res;
    }

    @Test
    public void test1() {
        int result = new MinSwapsCouples4()
                .minSwapsCouples(new int[]{0, 2, 1, 3});
        Assert.assertEquals(1, result);
    }

    @Test
    public void test2() {
        int result = new MinSwapsCouples4()
                .minSwapsCouples(new int[]{5, 4, 2, 6, 3, 1, 0, 7});
        Assert.assertEquals(2, result);
    }

    // 0, 2, 4, 6, 7, 1, 3, 5
    // 0, 1, 4, 6, 7, 2, 3, 5
    // 0, 1, 4, 5, 7, 2, 3, 6
    // 0, 1, 4, 5, 7, 6, 3, 2
    @Test
    public void test3() {
        int result = new MinSwapsCouples4()
                .minSwapsCouples(new int[]{0, 2, 4, 6, 7, 1, 3, 5});
        Assert.assertEquals(3, result);
    }
}
